\documentclass[11pt,a4paper,final,notitlepage]{article}
%\usepackage[latin1]{inputenc}
\usepackage{times}

\setlength{\hoffset}{0pt}  	
\setlength{\oddsidemargin}{0pt} 	% Marge gauche sur pages impaires
\setlength{\evensidemargin}{0pt} 	% Marge gauche sur pages paires
\setlength{\marginparwidth}{35pt} 	% Largeur de note dans la marge
\setlength{\textwidth}{450pt} 	% Largeur de la zone de texte (17cm)
\setlength{\marginparsep}{0pt} 	% Sparation de la marge
\setlength{\voffset}{0pt} 	% Bon pour DOS
\setlength{\topmargin}{0pt} 	% Pas de marge en haut
\setlength{\headheight}{0pt} 	% Haut de page
\setlength{\headsep}{0pt} 	% Entre le haut de page et le texte
\setlength{\footskip}{10pt} 	% Bas de page + sparation
\setlength{\textheight}{700pt} 	% Hauteur de la zone de texte (25cm) 
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{makeidx}
\usepackage{listings}
\usepackage{graphicx}

\title{Advanced Algorithms - Homework Set 2}
\author{Valentina Sintsova \{valentina.sintsova@epfl.ch\} \\ 
        Javier Picorel \{javier.picorel@epfl.ch\} \\
        Vasileios Trigonakis \{vasileios.trigonakis@epfl.ch\} \\}

\begin{document}

\maketitle

\thispagestyle{empty}
\pagestyle{empty}

\paragraph*{Question 3.} Array $A[1.. n]$ stores the height of $n$ buildings, indexed from west to east. Building $i$ has a good view of the sunrise if and only if every building to the east
of $i$ is shorter than $i$. Analyze the following algorithm (by bounding the amortized time spent in each iteration of the for loop) that computes which buildings
have a good view of the sunrise.
\begin{verbatim}
GOODVIEW(A[1 .. n]):
initialize a stack S
    for i :1 to n
        while (S not empty and A[i] > A[TOP(S)])
            POP(S)
        PUSH(S, i)
return S
\end{verbatim}
\\\\\\
We will use the aggregate method for calculating the amortized cost.
Assume that every \texttt{not empty}, comparison, \texttt{TOP, POP}, and \texttt{PUSH} operation cost 1. Then , we know that every iteration of the loop costs at least 1 \texttt{not empty}, 1 \texttt{TOP}, 1 comparison, and 1 \texttt{PUSH}, so 4 in total. Thus, all $n$ iterations cost for sure $4n$.

Now, we know that before entering the for loop the stack is empty, so the number of calls to \texttt{POP} in all iterations is bounded by the number of calls to \texttt{PUSH} minus 1\footnote{the last iteration (when $i = n$) will call \texttt{PUSH} and this \texttt{PUSH} will not be popped in any case}. Moreover, every call to \texttt{POP} means that one extra \texttt{not empty}, one comparison, and one \texttt{TOP} will run\footnote{this cost account for the extra successful check} (maximum $3(n - 1)$ cost).

Therefore, all operations in total will cost less or equal with: $4n + n - 1 + 3(n - 1) = 8n - 4 = O(n)$. Consequently, the amortized cost of each iteration is $O(n)/n = O(1)$.


\paragraph*{Question 4.} Analyze the process of generating all permutations of a sequence of distinct numbers lexicographically. The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.
\begin{itemize}
\item[] Find the largest index $k$ such that $a[k] < a[k+1]$. If no such index exists, exit
(the permutation is the last permutation).
\item[] Find the largest index $l$ such that $a[k] < a[l]$.
\item[] Swap $a[k]$ with $a[l]$.
\item[] Reverse the sequence from $a[k+1]$ up to and including the final element $a[n]$.
\end{itemize}
\\\\
Define the potential to be three times the length of the longest contiguously decreasing
subsequence at the end of the sequence.
\\\\\\
Let $L$ be the length of the longest contiguously decreasing subsequence at the end of the sequence, so that $\Phi = 3 * L$. Enumerate the steps of the algorithm as following:

\begin{enumerate}
\item Find the largest index $k$ such that $a[k] < a[k+1]$. If no such index exists, exit
(the permutation is the last permutation).
\item Find the largest index $l$ such that $a[k] < a[l]$.
\item Swap $a[k]$ with $a[l]$.
\item Reverse the sequence from $a[k+1]$ up to and including the final element $a[n]$.
\end{enumerate}

Then we have that:

\begin{itemize}
\item \textbf{Step 1.} Starting from the end of the array, finding the largest index $k$ needs $L$ steps, plus one for the $a[k]$ element\footnote{the failed comparison}. This step does not change the array, so it has $\Delta\Phi = 0$.
\item \textbf{Step 2.} Starting from element $k$ this step may need up to $L$ steps. It also does not change the potential ($\Delta\Phi = 0$).
\item \textbf{Step 3.} Swap takes constant time to execute. We do not account the change on the potential that swap causes because it will be included in the next step's $\Delta\Phi$.
\item \textbf{Step 4.}	The reverse costs $L$ and reverses the contiguously decreasing subsequence, thus creating an ascending subsequence of length $L$. So, $\Phi_{i} = 3L, \Phi_{i+1} = 3 \Rightarrow \Delta\Phi = -3L + 3$.
\end{itemize}

So, the amortized cost of a generating a single permutation is $L + 1 + L + 1 + L + (-3L + 3) = 3L + 2 - 3L + 2 = 5 = O(1)$. Now, the process of generating all permutations takes $n! - 1$ repetitions of the algorithm, therefore we have a total amortized cost of $O(n!)$.

Notice that the ``full'' algorithm for producing the permutations would firstly sort the sequence in ascending order (costs $O(nlogn)$) and then input the sorted array in the permutation generation algorithm. So, $\Phi_{0} = 3$, $\Phi_{n!-1} = 3n$, and $\Phi_{i} \geq 3$, $\forall i$ in $\{1\ldots n!-1\}$.
\end{document}